The present invention relates to packet switching networks and, more particularly, to route selection and path balancing in connection-oriented packet switching networks.
In a connection-oriented packet switching network, an example of which includes an X.25 packet network (as well as an Asynchronous Transfer Mode (ATM) network, which can operate in a connection-oriented environment), virtual circuits or connections are established before traffic can be sent on them. A connection-oriented packet switching network consists of switching nodes interconnected by transmission link groups, each of which comprises any number of parallel transmission links. When the network establishes a connection, the network selects a route that may go through a number of intermediate switching nodes. The route consists of active traffic paths established on the transmission link groups connecting the switching nodes along the route. Each traffic path is established on one transmission link between a pair of nodes.
Within each transmission link group, the network traffic among transmission links should be balanced to enhance congestion management capability, fault recovery, and quality of service to name a few. Decisions as to how to balance paths within a transmission link group may be made during route selection by a single node such as the source node. One disadvantage with this approach is that the view any single switching node has of the entire network is likely outdated. As a result of network delay, the node may be unaware of the establishment of new connections and the termination of old connections since the last update of the switching node.
A better alternative is to make path balancing decisions at transmission links as paths are being established on each transmission link group. Although basing balancing decisions as paths are being established uses up-to-date information about other active paths on the transmission link group, terminating connections or adding new transmission links to transmission link groups may cause an imbalance if path balancing decisions are made only when new paths are established.
Traffic may also become unbalanced when a transmission link fails. When a link fails, traffic from the failed link may be rerouted to other links in the transmission link group. Unless traffic is rerouted to that link upon its restoration to service, traffic may not be balanced among the links in the transmission link group.
It is, therefore, desirable to redistribute established, active traffic paths in transmission link groups in a connection-oriented packet switching network to balance the traffic paths among the transmission links in the transmission link groups. It is even more desirable to redistribute established, active paths in a transmission link group to reduce variance in utilization of path resources, such as bandwidth, CPU, and/or memory between links of a group. It is also desirable to redistribute established, active paths in a transmission link group to reduce variance in average utilization of path resources between links of a group on a per link basis.